package leetcode016;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/3sum-closest/
 */
public class Study016 {
    public int threeSumClosest(int[] nums, int target) {
        int result = -1;
        int minGap = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            //跳过相同的数值
            if (i > 0 && nums[i] == nums[i - 1]) continue;
           // if (nums[i] > target &&  nums[i] - target  > minGap) break;
            for (int j = i + 1; j < nums.length - 1; j++) {
                //跳过相同的数值
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                //if ( nums[i] + nums[j] > target &&  nums[i] + nums[j] - target  > minGap) break;
                int preSum = nums[i] + nums[j] + nums[nums.length - 1];
                int preGap = target - preSum;
                for (int k = nums.length - 2; k > j; k--) {
                    int sum = nums[i] + nums[j] + nums[k];
                    int gap = target - sum;
                    if (Math.abs(gap) > Math.abs(preGap)) {
                        break;
                    }
                    preSum = sum;
                    preGap = gap;
                }
                if (Math.abs(preGap) < minGap) {
                    minGap = Math.abs(preGap);
                    result = preSum;
                }
            }
        }
        return result;
    }

    public int threeSumClosest2(int[] nums, int target) {
        int result = 0;
        int minGap = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
                if (Math.abs(sum - target) < minGap) {
                    minGap = Math.abs(sum - target);
                    result = sum;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Study016 study016 = new Study016();
        System.out.println(study016.threeSumClosest(new int[]{4,0,5,-5,3,3,0,-4,-5}, -2));
        System.out.println(study016.threeSumClosest(new int[]{-100,-98,-2,-1}, -101));
    }
}
